package 链表.单链表crud;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList sll = new SingleLinkedList();
        HeroNode2 heroNode1 = new HeroNode2(1, "虚空掠夺者");
        HeroNode2 heroNode2 = new HeroNode2(2, "风暴之怒");
        HeroNode2 heroNode3 = new HeroNode2(3, "盖伦");
        HeroNode2 heroNode4 = new HeroNode2(4, "寒冰");

        sll.add(heroNode2);
        sll.add(heroNode3);
        sll.add(heroNode1);
        sll.add(heroNode4);

//        sll.update(new HeroNode(3,"德玛西亚"));
//        sll.del(4);
        sll.query();
        System.out.println("倒数第x个节点为====>" + sll.getLastNoNode(sll.getHead(), 3));

//        sll.reverseSingleLinkedList(sll.getHead());
        sll.reverseSingleLinkedListStack(sll.getHead());
//        sll.query();
    }
}

class HeroNode2 {
    public int id;
    public String name;
    public HeroNode2 next;

    public HeroNode2(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

class SingleLinkedList {
    public HeroNode2 head = new HeroNode2(0, "");

    public HeroNode2 getHead() {
        return head;
    }

    // 增
    public void add(HeroNode2 heroNode) {
        HeroNode2 curr = head;
        boolean isRepeated = false;
        while (true) {
            if (curr.next == null) { // 在末尾也可以去加
                break;
            }
            if (curr.next.id > heroNode.id) { // 找到则退出循环去加
                break;
            }
            if (curr.next.id == heroNode.id) {
                isRepeated = true;
                break;
            }
            curr = curr.next;
        }
        // 为了防止添加重复节点，这里做判断
        if (isRepeated) {
            System.out.printf("英雄编号%d已重复，不可重复添加~", heroNode.id);
        }
        heroNode.next = curr.next; // 这样写
        curr.next = heroNode;

//        curr.next = heroNode; // 这样写 则改变了当前节点的下一个节点
//        heroNode.next = curr.next;
    }

    // 删
    public void del(int id) {
        HeroNode2 curr = head;
        boolean isExist = true;
        while (true) {
            if (curr.next == null) { // 特殊情况处理
                isExist = false;
                break;
            }
            if (curr.next.id == id) { // 满足情况退出
                break;
            }
            curr = curr.next;
        }
        if (!isExist) {
            System.out.printf("英雄编号%d不存在，没有可以删除的~", id);
        }
        curr.next = curr.next.next;
    }

    // 改
    public void update(HeroNode2 heroNode) {
        HeroNode2 curr = head;
        boolean isExist = true;
        while (true) {
            if (curr.next == null) { // 特殊情况处理
                isExist = false;
                break;
            }
            if (curr.next.id == heroNode.id) { // 满足情况退出
                break;
            }
            curr = curr.next;
        }
        if (!isExist) {
            System.out.printf("英雄编号%d不存在，没有可以修改的", heroNode.id);
        }
        curr.next.name = heroNode.name;
    }

    // 查
    public void query() {
        if (head.next == null) {
            return;
        }
        HeroNode2 curr = head.next;
        while (true) {
            if (curr == null) { // 到链表最后一个的下一个即为null
                break;
            }
            System.out.println(curr);
            curr = curr.next;
        }
    }

    // 获取单链表倒数第x个节点
    public HeroNode2 getLastNoNode(HeroNode2 head, int x) {
        HeroNode2 curr = head;
        if (curr.next == null) {
            return null;
        }
        int length = 0;
        while (true) {
            if (curr.next == null) {
                break;
            }
            length++;
            curr = curr.next;
        }
        curr = head.next;
        for (int i = 0; i < length - x; i++) {
            curr = curr.next;
        }
        return curr;
    }

    // 反转单链表
    public void reverseSingleLinkedList(HeroNode2 head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        HeroNode2 curr = head.next;
        HeroNode2 next;
        HeroNode2 newReverseHead = new HeroNode2(0, "");

        while (true) {
            if (curr == null) { // 遍历到最后一个节点，下一个节点为空则退出循环
                break;
            }
            next = curr.next;
            curr.next = newReverseHead.next; // 插入节点1
            newReverseHead.next = curr; // 插入节点2，与新链表头节点建立连接
            curr = next;
        }
        head.next = newReverseHead.next;
    }

    // 从尾到头打印单链表，利用栈，不破坏链表结构
    public void reverseSingleLinkedListStack(HeroNode2 head) {
        HeroNode2 curr = head.next;
        Stack<HeroNode2> stack = new Stack<>();
        while (true) {
            if (curr == null) {
                break;
            }
            stack.push(curr);
            curr = curr.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}



